/*
*	滑动窗口练习
*/


//长度最小的子数组
//https://leetcode.cn/problems/minimum-size-subarray-sum/submissions/
//class Solution {
//public:
//    int minSubArrayLen(int target, vector<int>& nums) {
//        int n = nums.size();
//        int left = 0, right = 0;
//        int ret = INT_MAX;
//        int sum = 0;
//        while (right < n)
//        {
//            sum += nums[right];
//            //发现满足条件的sum
//            while (sum >= target)
//            {
//                //求取长度 取最小值
//                ret = min(ret, right - left + 1);
//                //left-1 同时减掉left下的数 保持滑动窗口区间的数和
//                sum -= nums[left++];
//            }
//            ++right;
//        }
//        return ret == (INT_MAX) ? 0 : ret;
//    }
//};


//无重复字符的最长子串
//https://leetcode.cn/problems/longest-substring-without-repeating-characters/submissions/
// class Solution {
// public:
//     int lengthOfLongestSubstring(string s) {
//         char hash[128] = {0};
//         int n = s.size();
//         int left = 0,right = 0;
//         int ret = 0;
//         while(right < n)
//         {
//             ++hash[s[right]];
//             //碰到重复字符
//             while(hash[s[right]] > 1)
//                 --hash[s[left++]];
            
//             ret = max(ret,right-left+1);
//             ++right;
//         }
//         return ret;
//     }
// };


//最大连续1的个数 III
//https://leetcode.cn/problems/max-consecutive-ones-iii/submissions/
// class Solution {
// public:
//     int longestOnes(vector<int>& nums, int k) {
//         int n = nums.size();
//         int left = 0,right = 0;
//         int ret = 0;
//         int zero = 0;
//         while(right < n)
//         {
//             if(nums[right] == 0) ++zero;
//             while(zero > k)
//                 if(nums[left++] == 0) --zero;

//             ret = max(ret,right-left+1);
//             ++right;
//         }
//         return ret;
//     }
// };


//将x减到0的最小操作数
//https://leetcode.cn/problems/minimum-operations-to-reduce-x-to-zero/submissions/
// class Solution {
// public:
//     int minOperations(vector<int>& nums, int x) {
//         //既然在数组的两边 可以将问题转换
//         //求数组中可以凑出 数组和-x 的子数组

//         //求和
//         int sum = 0;
//         for(int& a:nums) sum+=a;

//         int n = nums.size();
//         int left = 0, right = 0;
//         //求取需要凑出的子数组大小
//         int target = sum-x;
//         //如果x比整个数组还大 则找不到
//         if(target < 0) return -1;
//         int tmp = 0;
//         int ret = -1;
//         while(right < n)
//         {
//             tmp += nums[right];
//             while(tmp > target)
//                 tmp -= nums[left++];
//             if(tmp == target) ret = max(ret,right-left+1);
//             ++right;
//         }
//         return ret == -1?-1:n-ret;
//     }
// };


//水果成篮
//https://leetcode.cn/problems/fruit-into-baskets/submissions/
// class Solution {
// public:
//     int totalFruit(vector<int>& fruits) {
//         int n = fruits.size();
//         int hash[100001] = {0};
//         int left = 0,right = 0;
//         int kinds = 0;//水果种数
//         int ret = 0;
//         while(right < n)
//         {
//             if(hash[fruits[right]] == 0) ++kinds;
//             ++hash[fruits[right]];
//             while(kinds > 2)
//             {
//                 --hash[fruits[left]];
//                 if(hash[fruits[left]] == 0) --kinds;
//                 ++left;
//             }
//             ret = max(ret,right-left+1);
//             ++right;
//         }
//         return ret;
//     }
// };


//438.找到字符串中所有字母异位词
//https://leetcode.cn/problems/find-all-anagrams-in-a-string/submissions/
// class Solution {
// public:
//     vector<int> findAnagrams(string s, string p) {
//         vector<int> ret;
//         int hash1[26] = {0};
//         int hash2[26] = {0};
//         for (const auto& c : p) ++hash1[c - 'a'];

//         int plen = p.size();
//         int slen = s.size();
//         int left = 0, right = 0;
//         int count = 0;

//         while (right < slen)
//         {
//             //如果有效字符未找满 则count++
//             if(++hash2[s[right] - 'a'] <= hash1[s[right] - 'a']) ++count;
//             ++right;
//             //字符串长度过长
//             if ((right-left) > plen)
//             {
//                 //如果当前去掉的字符是有效字符则--count
//                 if(hash2[s[left] - 'a']-- <= hash1[s[left]-'a']) --count;
//                 ++left;
//             }

//             if (count == plen) ret.push_back(left);
//         }
//         return ret;
//     }
// };


//串联所有单词的子串
//https://leetcode.cn/problems/substring-with-concatenation-of-all-words/submissions/
// class Solution {
// public:
//     vector<int> findSubstring(string s, vector<string>& words) {
//         vector<int> ret;
//         unordered_map<string, int> hash1;
//         unordered_map<string, int> hash2;

//         for (const auto& wd : words) ++hash1[wd];

//         int len = words[0].size();
//         int slen = s.size();
//         int wlen = words.size();
//         int count = 0; //有效(words匹配单词个数)单词个数
//         for (int i = 0; i < len; ++i)
//         {
//             int left = i, right = i;
//             while (right < slen)
//             {
//                 string rstr = s.substr(right, len);
//                 //有效单词进入哈希表
//                 if(hash1.count(rstr))
//                     if (++hash2[rstr] <= hash1[rstr]) ++count;

//                 right += len;
//                 while (((right - left) / len) > wlen)
//                 {
//                     string lstr = s.substr(left, len);
//                     if (hash1.count(lstr))
//                         if (hash2[lstr]-- <= hash1[lstr]) --count;
//                     left += len;
//                 }
//                 if (count == wlen) ret.push_back(left);
//             }
//             hash2.clear();
//             count = 0;
//         }
//         return ret;
//     }
// };


//最小覆盖子串
//https://leetcode.cn/problems/minimum-window-substring/submissions/
// class Solution {
// public:
//     string minWindow(string s, string t) {
//         int sn = s.size();
//         int tn = t.size();
//         int hash1[128] = { 0 };
//         int hash2[128] = { 0 };
//         int kinds = 0; //t字符串中字符的种类
//         for (const auto& c : t) 
//             if(hash1[c]++ == 0) ++kinds;

//         int left = 0, right = 0;
//         int pos = -1, len = 10e5 + 10; //返回的结果区间
//         int count = 0; //字母的种类
//         while (right < sn)
//         {
//             char in = s[right];
//             if (++hash2[in] == hash1[in]) ++count;
//             while (count >= kinds)
//             {
//                 if ((right - left + 1) < len)
//                 {
//                     pos = left;
//                     len = (right - left + 1);
//                 }
//                 char out = s[left++];
//                 if (hash2[out]-- == hash1[out]) --count;
//             }
//             ++right;
//         }
//         return pos == -1 ? "" : s.substr(pos, len);
//     }
// };

